//#define _CRT_SECURE_NO_WARNINGS 1
//#include<iostream>
//#include<string>
//#pragma once
//using namespace std;
//
//#define MAXNUM 100
//typedef string VerTex;
//
//// 图的邻接矩阵
//typedef struct {
//	int arcnum, vexnum;
//	VerTex vex[MAXNUM]; // 存储顶点的数组
//	int arcs[MAXNUM][MAXNUM];
//}Graph;
//
//// 存储顶点集U到V-U的权值最小的边的辅助数组
//typedef struct {
//	VerTex adjvex; // 最小边在U中的顶点
//	int lowcast;  // 最小边上的权值
//}MinEdge;
//
//MinEdge closedge[MAXNUM];
//
//int LocateVex(const Graph& G, VerTex v) {
//	for (int i = 0; i < G.vexnum; i++) {
//		if (G.vex[i] == v)
//			return i;
//	}
//	return -1;
//}
//
//// 构建无向图
//void CreateGraph(Graph& G) {
//	cin >> G.vexnum >> G.arcnum;
//	// 依次输入顶点信息
//	for (int i = 0; i < G.vexnum; i++)
//		cin >> G.vex[i];
//	// 初始化邻接矩阵
//	for (int i = 0; i < G.arcnum; i++)
//		for (int j = 0; j < G.arcnum; j++)
//			G.arcs[i][j] = INT32_MAX;
//	for (int k = 0; k < G.arcnum; k++) {
//		VerTex v1, v2;
//		int w, i, j;
//		cin >> v1 >> v2 >> w;
//		// 查找位置
//		i = LocateVex(G, v1);
//		j = LocateVex(G, v2);
//		G.arcs[i][j] = G.arcs[j][i] = w;
//	}
//}
//
//// 在辅助数组中找到lowcost最小的顶点
//int MinCost(MinEdge closedge[], int size) {
//	// 取出最小权值边的顶点
//	int k = -1;
//	for (int i = 0; i < size; i++) {
//		// i号顶点并未被归入到生成树中
//		if (closedge[i].lowcast > 0) {
//			// min 存放最小权值
//			int min = closedge[i].lowcast;
//			for (int j = i; j < size; j++) {
//				if (closedge[j].lowcast > 0 && min >= closedge[j].lowcast){
//					min = closedge[j].lowcast;
//					k = j;
//				}
//			}
//			break;
//		}
//	}
//	return k;
//}
//
//// prim算法
//void Prim(Graph& G, VerTex u) {
//	// 先找到 v 的下标
//	int k = LocateVex(G, u);
//	// 对V-U中的每一个顶点，初始化closedge
//	for (int j = 0; j < G.vexnum; j++) {
//		closedge[j].adjvex = u;
//		closedge[j].lowcast = G.arcs[k][j];
//	}
//	// 初始化 U 中只有 u
//	closedge[k].lowcast = 0;
//	for (int i = 1; i < G.vexnum; i++) {
//		int k = MinCost(closedge, G.vexnum);
//		// u0为最小边的一个顶点,u0属于u, v0为最小边的另一个顶点，v0属于V-U
//		int u0 = closedge[k].lowcast;
//		VerTex v0 = G.vex[k];
//		cout << u0 << " " << v0 << endl;
//		// 将第 k 个结点并入U集合
//		closedge[k].lowcast = 0;
//		// 新顶点并入U后重新选择最小边
//		for (int j = 0; j < G.vexnum; j++) {
//			if (G.arcs[k][j] < closedge[j].lowcast) {
//				closedge[j].adjvex = G.vex[k];
//				closedge[j].lowcast = G.arcs[k][j];
//			}
//		}
//	}
//}

//int main() {
//	Graph G;
//	CreateGraph(G);
//	int v = 0;
// 	cout << "The minimum spanning tree obtained by Prim algorithm is as follows" << endl;
//	Prim(G, G.vex[v]);
//	return 0;
//}
